メモリの無駄遣いは、具体的にどの程度実行速度をスローダウンさせるか? 【▲→川俣晶の縁側→ソフトウェア→技術雑記】

　CPUより、キャッシュに乗っていないデータへのアクセスが発生するとスローダウンするが、キャッシュの容量は限られている。だから、プログラムやデータをムダに大きくすると実行速度をスローダウンさせる。

　……と言われることがよくありますが、どの程度のスローダウンが発生するのでしょうか。

　ちょっと気になったので簡単に検証。

題目 §

C# 3.5で書く (変な最適化をさせないためにデバッグビルドで実行)
byte配列を確保するが、nバイトごとにのみアクセスし、その間の要素は一切使わない。つまり、1要素ごとに(n-1)バイトのムダなメモリを上乗せする
nは1,2,4,8,1024とする
アクセスはランダムアクセスとし、アクセスする要素は乱数を用いてランダムな順番を決定する (シーケンシャルにアクセスするとn=1,2,4の値が大差なかったので、ランダムにやらせてみた)

サンプルソース §

using System;

class Program

{

private static void test(int size, int leave)

{

Random random = new Random(0);

int[] randomMap = new int[size];

for (int i = 0; i < size; i++)

randomMap[i] = random.Next(size) * leave;

byte[] ar = new byte[size * leave];

DateTime start = DateTime.Now;

int sum = 0;

for (int j = 0; j < 10000; j++)

{

for (int i = 0; i < size; i++)

ar[randomMap[i]] = 1;

for (int i = 0; i < size; i++)

sum += ar[randomMap[i]];

}

Console.WriteLine("time={0} leave={1} sum={2}",

DateTime.Now - start, leave, sum);

}

static void Main(string[] args)

{

int size = 100000;

test(size, 1);

test(size, 2);

test(size, 4);

test(size, 8);

test(size, 1024);

}

実行結果 §

time=00:00:14.5490000 leave=1 sum=1000000000

time=00:00:14.5230000 leave=2 sum=1000000000

time=00:00:18.9920000 leave=4 sum=1000000000

time=00:00:23.8240000 leave=8 sum=1000000000

time=00:01:52.1110000 leave=1024 sum=1000000000

考察 §

　ムダ無しよりも2バイト(1バイトのムダあり)の方が速いのは、単純に誤差の範囲ということでしょう。たぶん。

　しかし、4バイト(3バイトのムダあり)の方は、おそらく意味のある歴然とした差が出ています。

　従って、以下のような結論を出せることになります。

整数の配列にランダムな順序でアクセスする場合、要素の値がbyte型で表現可能な範囲に限られるとすれば、int型からbyte型に変更することで体感可能なスピードアップが実現される可能性がある (ただし、この処理に限れば、であってプログラム全体で体感可能なスピードアップになるかは別問題)

　(もちろん、仮想記憶のスワップ頻度も関係するなら、short→byteでもスピードアップの可能性があり得ますが、それはまた別の問題です)